package com.cat.dataStructure02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/
 * @create 2025/10/28 21:47
 * @since JDK17
 */

public class Solution78 {
    /**
     * @author 曲大人的喵
     * @description https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/
     * @create 2025/10/28 20:45
     * @since JDK17
     */

    public class Solution {
        int cnt;
        public int kthSmallest(int[][] mat, int k) {
            int min = 0, max = 0, n = mat.length, m = mat[0].length;
            for (int i = 0; i < n; i++) {
                min += mat[i][0];
                max += mat[i][m - 1];
            }
            int l = min - 1, r = max + 1;
            while (l + 1 < r) {
                int mid = l + r >> 1;
                cnt = k;
                if (check(mat, n - 1, mid - min)) {
                    r = mid;
                } else {
                    l = mid;
                }
            }

            return r;
        }

        boolean check(int[][] mat, int i, int rest) {
            if (i < 0) {    // 小于的
                return --cnt == 0;
            }
            for (int x : mat[i]) {  // 开始选数字
                if (x - mat[i][0] > rest) { // 选不了这个数字，会超出原定的
                    break;
                }
                if (check(mat, i - 1, rest - (x - mat[i][0]))) {    // >= k 直接返回true即可
                    return true;
                }
            }

            return false;
        }
    }

}
